#include <cstdlib>
#include <iostream>

#include <vector>
#include <set>
#include <string>
#include <sstream>

typedef std::set<int> TNumberSet;

std::string set_to_string(TNumberSet & numSet)
{
    std::stringstream output;
    output << "[";
    for(TNumberSet::iterator i = numSet.begin(); i != numSet.end(); i++)
    {
        if(i != numSet.begin())
        {
            output << ",";
        }
        output << (* i);
    }
    output << "]";
    return output.str();
}

typedef std::vector<TNumberSet> TNumberSetList;

void append_setlist(TNumberSetList & setListDest, TNumberSetList & setListSrc)
{
    for(TNumberSetList::iterator idx = setListSrc.begin(); idx != setListSrc.end(); idx++)
    {
        setListDest.push_back(* idx);
    }
}

typedef std::vector<int> TNumberList;

void get_subset(TNumberList & numList, int nBeginIdx, int nLen, TNumberSetList & setList)
{
    if(nLen - nBeginIdx == 0)
    {
        return;
    }

    int nCurrentNum = numList[nBeginIdx];
    get_subset(numList, nBeginIdx + 1, nLen, setList);

    TNumberSetList new_setList;
    append_setlist(new_setList, setList);
    for(TNumberSetList::iterator idx = new_setList.begin(); idx != new_setList.end(); idx++)
    {
        TNumberSet & numSet = (* idx);
        numSet.insert(numSet.begin(), nCurrentNum);
    }

    TNumberSet self_set;
    self_set.insert(nCurrentNum);
    new_setList.insert(new_setList.begin(), self_set);

    append_setlist(setList, new_setList);
}

int main(int argc, char *argv[]) {
    std::cout << "Welcome to the subset calculation" << std::endl;

    TNumberList numList;
    numList.push_back(1);
    numList.push_back(2);
    numList.push_back(5);
    numList.push_back(7);

    TNumberSetList numSetList;
    get_subset(numList, 0, numList.size(), numSetList);
    for(TNumberSetList::iterator i = numSetList.begin(); i != numSetList.end(); i++)
    {
        std::string s = set_to_string(* i);
        std::cout << s << std::endl;
    }

    return EXIT_SUCCESS;
}
